#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2021/01/08
# @Author   :Changshu
# @File     :Exercise_653.py
# 653. 两数之和 IV - 输入 BST
# 给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

# Definition for a binary tree node.
class TreeNode:
	def __init__(self, val=0, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right


class Solution:
	def findTarget(self, root: TreeNode, k: int) -> bool:
		s = set()

		def find(root: TreeNode, k: int, s: set) -> bool:
			if not root:
				return False
			if k - root.val in s:
				return True
			s.add(root.val)
			return find(root.left, k, s) or find(root.right, k, s)

		return find(root, k, s)


if __name__ == '__main__':
	root = TreeNode(5)
	node2_1 = TreeNode(3)
	node2_2 = TreeNode(6)
	node3_1 = TreeNode(2)
	node3_2 = TreeNode(4)
	node3_3 = TreeNode(7)

	root.left=node2_1
	root.right=node2_2
	node2_1.left=node3_1
	node2_1.right=node3_2
	node2_2.right=node3_3

	solution = Solution()
	print(solution.findTarget(root, 9))
